/*
https://leetcode.cn/problems/count-numbers-with-unique-digits/
数位dp
*/
class Solution {
public:
    // 函数 countDigitOne 接受一个整数 n 作为参数，
    // 返回从 1 到 n 之间所有整数中数字 1 出现的总次数。
    int countDigitOne(int n) {
        if (n == 0) return 0;  // 如果 n 为 0，直接返回 0

        int ans = 0;  // 用于记录 1 出现的总次数
        long long DN = 1;  // 位权，初始为 1（个位）
        int lastNum = 0;  // 记录当前位后面的数字

        while (n / DN != 0) {
            // 获取当前位的数字
            int curbit = n / DN % 10;

            // 高一位的位权
            long long D = DN * 10;

            // 根据当前位的数字，分三种情况计算 1 的出现次数
            if (n % D == 0) {
                // 当前位及后面的数字都是 0，例如 3400 中十位上的 1
                ans += n / 10;
            } else if (curbit == 0) {
                // 当前位是 0，例如 3402 中十位上的 1
                ans += (n / D) * (D / 10);
            } else if (curbit >= 2) {
                // 当前位大于等于 2，例如 3421 中十位上的 1
                ans += ((n / D) + 1) * (D / 10);
            } else if (curbit == 1) {
                // 当前位是 1，例如 3415 中十位上的 1
                ans += (n / D) * (D / 10) + lastNum + 1;
            }

            // 更新 lastNum，加上当前位的值乘以当前位权
            lastNum += curbit * DN;

            // 位权乘以 10，进入下一位
            DN *= 10;
        }

        return ans;
    }
};